class Solution670 {
    public int maximumSwap(int num) {
        if (num<12) return num;
        int[] arr = new int[9];
        int[] stack = new int[9];
        int i = -1, s = -1;

        while (num!=0){
            i++;
            arr[i] = num%10;
            num = num / 10;
            s++;
            if (s==0) stack[s]=0;
            else if (arr[i]>arr[stack[s-1]]) stack[s]=i;
            else stack[s]=stack[s-1];
        }
        
        while (s!=0){
            if (arr[s]!=arr[stack[s]]){
                int tmp = arr[s];
                arr[s] = arr[stack[s]];
                arr[stack[s]] = tmp;
                break;
            }
            s--;
        }

        int res = 0;
        while (i >= 0){
            res = res*10+arr[i];
            i--;
        }
        return res;

    }
}